package problem1005;

import java.util.PriorityQueue;

//1005.k次取反后最大化的数组和
//https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int x : nums) {
            queue.add(x);
        }
        while(k-- > 0) {
            int x = queue.poll();
            queue.add(-x);
        }
        int sum = 0;
        while(!queue.isEmpty()) {
            sum += queue.poll();
        }
        return sum;
    }
}